/******************************************************************************
  DISCLAIMER:
  This software was produced by the National Institute of Standards
  and Technology (NIST), an agency of the U.S. government, and by statute is
  not subject to copyright in the United States.  Recipients of this software
  assume all responsibility associated with its operation, modification,
  maintenance, and subsequent redistribution.

  See NIST Administration Manual 4.09.07 b and Appendix I. 
*****************************************************************************/

#include <stdlib.h> // for NULL, exit

/*

This file provides a set of classes that may be used to build abstract
syntax trees for the DMIS language. The classes include enough methods
and data members to represent any language described using a subset of
EBNF, but they also include methods and data members needed to support
the complex processing done by debnf2pars.y.

The dialect of EBNF used in DMIS includes some typographical
conventions that extend EBNF. They are (invisibly) supported here
by providing a broad definition of the expression class. See the
documentation of the expression class for more details.

An EBNF file is a list of productions. Each production sets a
production name to be equivalent to a list of definitions. The
definitions are separated by vertical bars and the list is terminated
by a semicolon. Each definition is a list of expressions. An
expression in an EBNF file may be:
1. the name of a production
2. an optional
   An optional is represented by items inside square brackets.
   Example: [b c]
3. a repeated optional
   A repeated optional is represented by a positive integer followed by
   an asterisk, followed by items inside square brackets.
   Example: 3*[b c]
   This example means any of four things:
   (1) nothing  (2) b c  (3) b c b c  (4) b c b c b c
4. an optional list
   An optional is represented by items inside curly braces.
   Example: {b c}
   This example means either nothing or any number of repetitions of b c.
5. a terminal string
   A terminal string is represented by characters inside single quotes.
   Example: 'this is a terminal string'
6. a complex group of items.
   A complex group of items is represented by items inside parentheses
   Example: ('A'|'a')

The C++ classes defined in this file, together with the YACC/Lex parser
in the debnf2pars.y and debnf2pars.lex files, support all of the
functionality of EBNF except:
1. A complex group of items is not supported except for the very simple
   type of complex group shown in the example above.
2. The "except" symbol is not supported.

The curly braces {} notation for a possibly empty list is not supported.
This exception does not cause any loss of functionality because lists
can be fully represented another way without greatly increasing file
size or decreasing comprehensibility.

The ordering of the list of productions in an EBNF file and the
ordering of the list of definitions of a production are
irrelevant. The ordering of the list of expressions of a definition is
significant. In the C++ classes it is convenient to keep all lists
ordered so that they may be traversed easily. Definitions and
expressions lists may be empty. An empty productions list is possible
but pointless, since then there would be an empty file and no
language.

Each class defined here has one destructor that does nothing and two
constructors. The first constructor takes no arguments and does
nothing.  The second constructor takes arguments that are the same as
its data members and sets the data members to the arguments.

This file defines its own lists rather than using C++ lists. This is
done because doubly linked lists are used to enable traversal in
either direction. For each of the three list types, a listCell class
and a list class are defined. The listCell classes each have three
pointers: back (a listCell), next (a listCell), and data (an instance
of the class being listed). The list classes have two pointers to
listCells: last and first.

In each of the three list types, some of the following functions are
defined (see ebnfClasses.cc for more details):

findLength - finds the number of elements in a list; an empty list
has length zero.

insertAfterCell - adds an item in a new listCell that is inserted
immediately after the given listCell.

pushBack - adds an item in a new listCell that is inserted at the end
of the list.

pushFront - adds an item in a new listCell that is inserted at the front
of the list.

removeCell - removes the given cell from "this" list. The prodList
class also has removeProd, which removes (only) the cell containing
the first instance of a given production.

spliceInAfterCell - copies the contents of a "from" list into the
"this" list immediately after the given listCell.

spliceInFirst - copies the contents of a "from" list into the front
of "this" list.

Five class have a dup() method, which makes a duplicate of "this"
(see ebnfClasses.cc for more details).

The stringCell class is not needed for representing EBNF but is used
in debnf2pars.

*/

class definition;
class defListCell;
class defList;
class expression;
class expListCell;
class expList;
class optional;
class production;
class prodListCell;
class prodList;
class stringCell;

/********************************************************************/

/* class definition

A definition is a list of expressions.

The data member className exists so that the class for a definition is
known.

The data member newDefs exists so that a set of new definitions can be
associated with this definition. The newDefs of a definition are
derived from the definition.

*/

class definition
{
public:
  definition()
  {
    className = 0;
    expressions = 0;
    newDefs  = 0;
  }
  definition(char * classNameIn, expList * expressionsIn, defList * newDefsIn)
  {
    className = classNameIn;
    expressions = expressionsIn;
    newDefs  = newDefsIn;
  }
  ~definition(){}

  definition * dup();
  
  char * className;      // name of class to instantiate in action
  expList * expressions; // expressions giving the definition
  defList * newDefs;     // revised definitions to replace this
};

/********************************************************************/

/* class defListCell

This defines the type of doubly-linked cell used to make defLists.
Pointers are kept to the previous cell, to the next cell, and to a
definition.

*/

class defListCell
{
public:
  defListCell(){}
  defListCell(definition * def)
  {
    data = def;
    next = 0;
    back = 0;
  }
  ~defListCell(){}

  defListCell * next;
  defListCell * back;
  definition * data;
};

/********************************************************************/

/* class defList

This is a doubly-linked list type for definitions.  Pointers are kept
to the first and last cells.

If a list is not empty, first should point to the first cell in the
list, and last should point to the last cell in the list.

If a list is empty, first and last should both be set to NULL.

*/

class defList
{
public:
  defList()
  {
    first = 0;
    last = 0;
  }
  defList(definition * def)
  {
    defListCell * aCell;

    aCell = new defListCell(def);
    first = aCell;
    last = aCell;
  }
  ~defList(){}

  defList * dup();
  int findLength();
  void insertAfterCell(defListCell * defCell, definition * def);
  void pushBack(definition * def);
  void pushFront(definition * def);
  void removeCell(defListCell * listCell);

  defListCell * first;
  defListCell * last;
};

/********************************************************************/

/* class expression

The definition of expression is tailored so that it can represent
the following sorts of things from an EBNF file, according to the
value of theType:
   ENDLINE - pound sign, ie #
   KEYWORD - word in all upper case file, eg INNER
   NONTERMINAL - word with lower case first letter, eg assignStm
   ONECHAR - single character surround by apostrophes, eg '('
   OPTIONAL - expressions in square brackets, eg  [c , intVal]
   TERMINAL - word with upper case 1st letter, lower case 2nd, eg RealString
   TERMINALSTRING - two or more characters surround by apostrophes, eg '**'
   TWOCHAR - thing of the form ('D'|'d'), where any letter could be used

The optValue of an expression is set only if theType is OPTIONAL, and
in that case is set to an optional.

The prodValue of an expression is set only if theType is NONTERMINAL,
and in that case is set to the production whose name is itemName.

The itemName of an expression is set if theType is ENDLINE, KEYWORD,
NONTERMINAL, ONECHAR, TERMINAL, or TWOCHAR. For KEYWORD and NONTERMINAL,
the characters in the itemName string are exactly the characters in
the EBNF file. For ENDLINE, itemName is ENDLINE. For ONECHAR, itemName
is the character between the apostrophes. For TERMINAL, itemName is
the characters that were read converted to all upper case. For TWOCHAR,
itemName is the two letters.

The attName (attribute name) of an expression is set if the expression
corresponds to an attribute of a class that represents the definition
in which the expression is used.

Debnf2pars uses four special expressions: commaExp, trueExp, falseExp,
and nullExp. For these, the values of the data members are irrelevant
and may be garbage.

*/

class expression
{
public:
  expression()
  {
    theType = 0;
    itemName = 0;
    attName = 0;
    optValue = 0;
    prodValue = 0;
  }
  expression(int theTypeIn, char * itemNameIn, char * attNameIn,
	     optional * optValueIn, production * prodValueIn)
  {
    theType = theTypeIn;
    itemName = itemNameIn;
    attName = attNameIn;
    optValue = optValueIn;
    prodValue = prodValueIn;
  }
  ~expression(){}
  expression * dup();
  
  int theType;
  char * itemName;
  char * attName;
  optional * optValue;
  production * prodValue;
};

/********************************************************************/

/* class expListCell

This defines the type of doubly-linked cell used to make expLists.
Pointers are kept to the previous cell, to the next cell, and to an
expression.

*/

class expListCell
{
public:
  expListCell(){}
  expListCell(expression * exp)
  {
    data = exp;
    next = 0;
    back = 0;
  }
  ~expListCell(){}

  expListCell * next;
  expListCell * back;
  expression * data;
};

/********************************************************************/

/* class expList

This is a doubly-linked list type for expressions.  Pointers are kept
to the first and last cells.

If a list is not empty, first should point to the first cell in the
list, and last should point to the last cell in the list.

If the list is empty, first and last should both be set to NULL.

The "uses" method returns true if "this" expList contains an
expression whose itemName is the same as the name of the the "prod"
production. It also returns true if "this" explist contains an
optional and a recursive call of this method applied to the
expressions of the optional returns true. Otherwise, it returns false.

The "uses" method also inserts prod as the prodValue of any expression
in "this" list if the itemName of the expression is the same as the
name of the production.

*/

class expList
{
public:
  expList()
  {
    first = 0;
    last = 0;
  }
  expList(expression * exp)
  {
    expListCell * aCell;

    aCell = new expListCell(exp);
    first = aCell;
    last = aCell;
  }
  ~expList(){}

  expList * dup();
  int findLength();
  void insertAfterCell(expListCell * expCell, expression * exp);
  void pushBack(expression * exp);
  void pushFront(expression * exp);
  void removeCell(expListCell * expCell);
  void spliceInAfterCell(expListCell * expCell, expList * from);
  void spliceInFirst(expList * from);
  bool uses(production * prod);
  expression * nth(int n);

  expListCell * first;
  expListCell * last;
};

/********************************************************************/

/* class optional

An optional is a list of expressions whose usage is indicated by the
value of a digit.

The allowed values of digit are not restricted here, but the intended
usage is:
less than 0 is an error
equal to  0 means optional items repeated any number of times, e.g. {b c}
more than 0 means optional items repeated n times, e.g. 3*[b c]

For all of the examples above, the expressions would be [b c].
Note that 1*[b c] and [b c] are both allowed and they mean the
same thing (zero or one occurrence of b c).

*/

class optional
{
public:
  optional(){}
  optional(expList * expressionsIn, int digitIn)
  {
    expressions = expressionsIn;
    digit = digitIn;
  }
  ~optional(){}

  optional * dup();

  expList * expressions;
  int digit;
};

/********************************************************************/

/* class prodListCell

This defines the type of doubly-linked cell used to make prodLists.
Pointers are kept to the previous cell, to the next cell, and to a
production.

*/

class prodListCell
{
public:
  prodListCell()
  {
    data = 0;
    next = 0;
    back = 0;
  }
  prodListCell(production * prod)
  {
    data = prod;
    next = 0;
    back = 0;
  }
  ~prodListCell(){}

  prodListCell * next;
  prodListCell * back;
  production * data;
};

/********************************************************************/

/* class prodList

This is a doubly-linked list type for productions.  Pointers are kept
to the first and last cells.

If a list is not empty, first should point to the first cell in the
list, and last should point to the last cell in the list.

If the list is empty, first and last should both be set to NULL.

*/

class prodList
{
public:
  prodList()
  {
    first = 0;
    last = 0;
  }
  prodList(production * prod)
  {
    prodListCell * aCell;

    aCell = new prodListCell(prod);
    first = aCell;
    last = aCell;
  }
  ~prodList(){}

  int findLength();
  void findUsedIn();
  void insertAfterCell(prodListCell * prodCell, production * prod);
  void pushBack(production * prod);
  void removeCell(prodListCell * prodCell);
  void removeProd(production * prod);
  prodListCell * member(production * prod);

  prodListCell * first;
  prodListCell * last;
};

/********************************************************************/

/* class production

A production says the lhs (left-hand side) is equivalent to any of
the defs (definitions).

Several data members have been added for the convenience of applications.
See documentation of the methods in the ebnfClasses.cc file.

Note that since a production has a prodList as one of its attributes,
production must be defined after prodList.

endsInOptional, whose default value is false, should be set to true
when a production is first read from its EBNF file if and only if any
definition of the production ends with an optional that starts with a
comma.

*/

class production
{
public:
  production()
  {
    defs = 0;
    endsInOptional = false;
    fixType = fixNone;
    isList = 0;
    isSupertype = false;
    lhs = 0;
    subtypeOf.first = 0;
    subtypeOf.last = 0;
    usedIn.first = 0;
    usedIn.last = 0;
    wasPrinted = false;
  }
  production(char * lhsIn, defList * defsIn);
  ~production(){}
  
  enum fixTypeE {fixListItemDeleted,
		 fixListItemsInserted1,
		 fixListItemsInserted2,
		 fixNone,
		 fixProdC,
		 fixProdCUser};

  defList * defs;      // the definitions of the production
  bool endsInOptional; // see above
  fixTypeE fixType;    // the kind of fix that has been or should be applied
  int isList;          // 0=not a list, 1=list no commas, 2=list with commas
  bool isSupertype;    // true = this production is a supertype of other prods
  char * lhs;          // the name of the production (lhs = left-hand side)
  prodList subtypeOf;  // list of productions of which this is a subtype
  prodList usedIn;     // list of product'ns in which the name of this appears
  bool wasPrinted;     // true = classes for this production have been printed 

  int findInnerList();
  int findIsList();
  int findOuterList(production ** outerList);
  void findUsedIn(prodList * productions);
};

/********************************************************************/

/* class stringCell

This is a minimal list cell class for making lists of strings.
No stringList class is defined. The record method puts a string
into a list in alphabetical order.

*/

class stringCell
{
 public:
  stringCell(){data = 0; next = 0;}
  stringCell(char * dataIn)
    {data = dataIn; next = 0;}
  ~stringCell(){}

  void record(char * dataIn);
  
  char * data;
  stringCell * next;
};

/********************************************************************/

